package main

import "math/rand"

//抽样水池算法

type Solution struct {
	nums []int
}

func Constructor(nums []int) Solution {
	return Solution{nums}
}

func (this *Solution) Pick(target int) int {
	res := 0
	cnt := 0 //第cnt次遇到target
	for i, num := range this.nums {
		if num == target {
			cnt++
			if rand.Intn(cnt) == 0 { //每次遇到target时以1/cnt概率取当前索引
				res = i
			}
		}
	}
	return res
}
